package 蓝桥杯算法;

import 二叉树.TreeNode;
import 队列.LinkedListQueue;

import java.util.LinkedList;

import java.util.*;

public class day11 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                new TreeNode(
                        new TreeNode(4),
                        2,
                        new TreeNode(5)
                ),
                1,
                new TreeNode(
                        new TreeNode(6),
                        3,
                        new TreeNode(7)
                )
        );
        day11 a=new day11();
        List<Integer> result=a.checkFun(root);
       for(Integer i:result){
           System.out.println(i);
       }

    }
    static  class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
        public TreeNode(TreeNode left, int val, TreeNode right){//实参传递
            this.left=left;
            this.val=val;
            this.right=right;
        }
        @Override
        public String toString(){
            return String.valueOf(this.val);//打印
        }
    }

   public List<Integer> preorderTraversal(TreeNode root){
        List<Integer> result=new ArrayList<Integer>();//存储值的集合
        preorder(root,result);
        return result;
   }
   public void preorder(TreeNode root,List<Integer> result){
        if(root==null){
            return;
        }
        result.add(root.val);
        preorder(root.left,result);
        preorder(root.right,result);
   }
   public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> result=new ArrayList<>();
        inorder(root,result);
        return result;
   }
   public  void inorder(TreeNode root,List<Integer> result){
        if(root==null){
            return;
        }
        inorder(root.left,result);
        result.add(root.val);
        inorder(root.right,result);
   }
   public List<Integer> postorderTraversal1(TreeNode root){
        List<Integer> res=new ArrayList<>();
        postorder(root,res);
        return res;
   }
   public void postorder(TreeNode root,List<Integer> res){
        if(root==null){
            return;
        }
        postorder(root.left,res);
        preorder(root.right,res);
        res.add(root.val);
   }
   public  List<Integer>  preorderTraversal1(TreeNode root){//前序遍历
        List<Integer> result=new ArrayList<>();
        if(root==null){
            return result;
        }
       Stack<TreeNode> stack=new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node=stack.pop();
            result.add(node.val);
            if(node.right!=null){
                stack.push(node.right);
            }
            if(node.left!=null){
                stack.push(node.left);
            }
        }
        return result;
   }
   public List<Integer> inorderTraversal1(TreeNode root){
        List<Integer> result=new ArrayList<>();
        if(root==null){
            return result;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            if(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            else{
                cur=stack.pop();
                result.add(cur.val);
                cur=cur.right;
            }
        }
        return result;
   }
   public  List<Integer> postorderTraversal(TreeNode root){
     List<Integer> result=new ArrayList<>();
     if(root==null){
         return result;
     }
     Stack<TreeNode> stack=new Stack<>();
     stack.push(root);
     while(!stack.isEmpty()){
         TreeNode node =stack.pop();
         result.add(node.val);
         if(node.left!=null){
             stack.push(node.left);
         }
         if(node.right!=null){
             stack.push(node.right);
         }
     }
       Collections.reverse(result);
     return  result;
   }
   public List<Integer> checkFun(TreeNode node) {
       if (node == null) {
           return null;
       }
      LinkedList<TreeNode> queue=new LinkedList<>();
       queue.push(node);
       List<Integer> result = null;
       while (!queue.isEmpty()) {
           result = new ArrayList<>();
           int len = queue.size();
           while (len > 0) {
               TreeNode temnode = queue.poll();
               result.add(temnode.val);
               if (temnode.left != null) {
                   queue.offer(temnode.left);
               }
               if (temnode.right != null) {
                   queue.offer(temnode.right);
               }
               len--;
           }
       }
       return result;
   }
   public void checkFuun1(二叉树.TreeNode node,int deep){
        List<List<Integer>> resList=new ArrayList<List<Integer>>();
        if(node==null){
            return;
        }
        deep++;
        if(resList.size()<deep){
            List<Integer> item=new ArrayList<Integer>();
            resList.add(item);
        }
        resList.get(deep-1).add(node.val);
        checkFuun1(node.left,deep);
        checkFuun1(node.right,deep);

   }
}
